package com.justnow.dp;

/**
 * @author justnow
 * Created on 2020-09-22
 * Description
 * 连续子数组的最大值
 *
 *
 */
public class SwardOffer42 {
    public static void main(String[] args) {
        maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
    }
    public static int maxSubArray(int[] nums) {
        int length = nums.length;
        int max = nums[0]; //防止只有一个数字
        //dp[i]表示以nums[i]为结尾的连续子数组的最大和，也就是dp[i]中一定包含加数nums[i],
        //只有这样才能保证dp[i]到dp[i+1]的合法性。如果不包含 nums[i]nums[i] ，递推时则不满足题目的 连续子数组 要求。
        int[] dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            if (dp[i - 1] < 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i-1] + nums[i];
            }
            System.out.print(dp[i] + " ");
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
